package com.du.algorithm.primary;

import java.util.HashMap;
import java.util.Map;

/**
 * @desc: 基础题
 * @author: shuangdu
 * @date: 2022/12/21
 * @since: 1.8
 */
public class BasicSubject {

    /**
     * 无重复字符的最长子串
     * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
     *
     *
     * 示例 1:
     *
     * 输入: s = "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 示例 2:
     *
     * 输入: s = "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * 示例 3:
     *
     * 输入: s = "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     *
     *
     * 提示：
     *
     * 0 <= s.length <= 5 * 104
     * s 由英文字母、数字、符号和空格组成
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int maxLength = 0;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, i);
            maxLength = Math.max(maxLength, i - left + 1);
        }
        System.out.println("长度为:" + maxLength);
        return maxLength;
    }

    /**
     * 寻找两个正序数组的中位数
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     *
     * 算法的时间复杂度应该为 O(log (m+n)) 。
     *
     * 示例 1：
     *
     * 输入：nums1 = [1,3], nums2 = [2]
     * 输出：2.00000
     * 解释：合并数组 = [1,2,3] ，中位数 2
     * 示例 2：
     *
     * 输入：nums1 = [1,2], nums2 = [3,4]
     * 输出：2.50000
     * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
     *  
     *
     * 提示：
     *
     * nums1.length == m
     * nums2.length == n
     * 0 <= m <= 1000
     * 0 <= n <= 1000
     * 1 <= m + n <= 2000
     * -106 <= nums1[i], nums2[i] <= 106
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length - 1;
        int l2 = nums2.length - 1;
        int[] arr = new int[nums1.length + nums2.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            if (l1 < 0) {
                arr[i] = nums2[l2--];
            } else if (l2 < 0) {
                arr[i] = nums1[l1--];
            } else if (nums1[l1] > nums2[l2]) {
                arr[i] = nums1[l1--];
            } else {
                arr[i] = nums2[l2--];
            }
        }

//        System.out.println(Arrays.toString(arr));
        // 寻找中位数
        // 奇数个元素的中位数为最中间的元素
        // 偶数个元素的中位数为中间2个元素的平均值
        double mid = (arr.length & 1) == 0 ? (arr[arr.length / 2 - 1] + arr[arr.length / 2]) / 2.0 : arr[arr.length / 2];
        System.out.println("中位数为：" + mid);
        return  mid;
    }

    /**
     * 最长回文子串
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     *
     * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
     *
     * 示例 1：
     *
     * 输入：s = "babad"
     * 输出："bab"
     * 解释："aba" 同样是符合题意的答案。
     * 示例 2：
     *
     * 输入：s = "cbbd"
     * 输出："bb"
     *
     * 提示：
     *
     * 1 <= s.length <= 1000
     * s 仅由数字和英文字母组成
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        int strLength = s.length();
        int maxLength = 0;
        int maxStart = 0;
        int maxEnd = 0;
        boolean[][] dp = new boolean[strLength][strLength];
        for (int r = 1; r < strLength; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLength) {
                        maxLength = r - l + 1;
                        maxStart = l;
                        maxEnd = r;
                    }
                }
            }
        }

        System.out.println(maxStart + "-" + maxEnd);
        String word = s.substring(maxStart, maxEnd + 1);
        System.out.println("最长回文为：" + word);
        return word;
    }


    public static void main(String[] args) {

        LogTool.exec("无重复字符的最长子串", () -> lengthOfLongestSubstring("pwwkew"));

        LogTool.exec("寻找两个正序数组的中位数", () -> findMedianSortedArrays(new int[]{1, 3, 5, 9}, new int[]{2, 4, 5, 6}));

        LogTool.exec("最长回文子串", () -> longestPalindrome("bbb666bbb6bbb666bbb"));
    }
}
